import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.*;

/**
 * @author Xu,
 * @data 2020/11/15，
 * @time 9:18
 * 还差实现关联规则，
 */
public class Main{
    /**
     * 迭代次数
     */
    private static  int times=0;
    /**
     * 最小支持度；
     */
    private static final int MIN_SUP = 2;
    /**
     * 最小置信度；
     */
    private static final double MIN_CONF = 0.95;
    /**
     * 循环状态，迭代标识
     */
    private static boolean endTag = false;
    /**
     * 数据集
     */
    private static List<List<String>> data2DList = new ArrayList<List<String>>();
    /**
     * 存储所有的频繁项集
     */
    private static  List<List<String>> frequentItemset=new ArrayList<>();
    /**
     * 存放频繁项集和对应的支持度技术
     */
    private static List<Mymap> map = new ArrayList();
    /**
     * 默认最小支持度为2，最小置信度为0.6；
     *
     * @param args
     */
    public static void main(String[] args) {
        /**
         * 导入数据
         */
        importData();
        /**
         * 导出data2DList表查看是否读取txt成功；
         */
//        exportData();
        /**
         * 进行apriori算法
         */
        apriori();
        /**
         * 进行关联规则挖掘
         */
//        AssociationRulesMining();
    }

    /**
     * 导出数据集检测是否读取文件成功；
     */
    public static void exportData() {
        for (List<String> array : data2DList) {
            for (int i=0; i<array.size(); i++){
                System.out.print(array.get(i) + " ");
            }
            System.out.println();
        }
    }

    /**
     * 导入数据，将数据导入data2DList；
     *
     * @return null
     */
    public static void importData() {
        String path = "./src/data.txt";
        try {
            //文件存在且为文件类型执行接下来的操作
            InputStreamReader reader = new InputStreamReader(new FileInputStream(path),
                    "UTF-8");
            BufferedReader bufferedReader = new BufferedReader(reader);
            //注意：这里的lineTxt是加序号的；
            String lineTxt = null;
            while ((lineTxt = bufferedReader.readLine()) != null) {
                //读取文件中的一行，并添加到data2DList;
                String[] lineString = lineTxt.substring(3).split(" ");
                List<String> lineList = new ArrayList<String>();
                for(int i=0; i<lineString.length; i++){
                    lineList.add(lineString[i]);
                }
                data2DList.add(lineList);
            }
            reader.close();
        } catch (Exception e) {
            System.out.println("读取文件内容出错！");
            e.printStackTrace();
        }
    }

    /**
     * apriori算法主程序
     * @return null
     */
    public static void apriori() {
        //************获取候选1项集**************
        List<List<String>> candidateItemset = findFirstCandidate();

        //************获取频繁1项集***************
        System.out.println("***************第1次扫描后频繁集****************");
        List<List<String>> frequentItemset = getSupprotedItemset(candidateItemset);
        /**
         * 添加到所有的频繁项集中
         */
        AddToFrequenceItem(frequentItemset);
        /**
         * 控制台输出1项频繁集
         */
        ShowData(frequentItemset);


        //*****************************迭代过程**********************************
        times=2;
        while(endTag!=true){

            List<List<String>> nextCandidateItemset = getNextCandidate(frequentItemset);

            /**************计数操作***由候选k项集选择出频繁k项集****************/
            System.out.println("***************第"+times+"次扫描后频繁集****************");
            List<List<String>> nextFrequentItemset = getSupprotedItemset(nextCandidateItemset);
            /**
             * 排序
             */

            /**
             * 添加到所有的频繁项集中
             */
            AddToFrequenceItem(nextFrequentItemset);
            //输出所有的频繁项集
            ShowData(nextFrequentItemset);


            //*********如果循环结束，输出最大模式**************
            if(endTag == true){
                System.out.println("\n\n\nApriori算法--->最大频繁集=============================");
                ShowData(frequentItemset);
            }
            //****************下一次循环初值********************
            frequentItemset = nextFrequentItemset;
            times++;//迭代次数加一
        }
    }

    /**
     * 关联规则挖掘
     * 本程序尚不使用；
     */
    public static void AssociationRulesMining()
    {
        for(int i=0;i<frequentItemset.size();i++)
        {
            List<String> tem=frequentItemset.get(i);
            if(tem.size()>1) {
                List<String> temclone=new ArrayList<>(tem);
                /**
                 * 得到频繁项集tem的所有子集
                 */
                List<List<String>> AllSubset = getSubSet(temclone);
                for (int j = 0; j < AllSubset.size(); j++) {
                    List<String> s1 = AllSubset.get(j);
                    List<String> s2 = gets2set(tem, s1);
                    double conf = isAssociationRules(s1, s2, tem);
                    if (conf > 0) {
                        System.out.println("置信度为：" + conf);
                    }
                }
            }

        }
    }

    /**
     * 判断是否为关联规则
     * @param s1
     * @param s2
     * @param tem
     * @return
     */
    public  static  double isAssociationRules(List<String> s1,List<String> s2,List<String> tem)
    {
        double confidence=0;
        int counts1;
        int countTem;
        if(s1.size()!=0&&s1!=null&&tem.size()!=0&&tem!=null)
        {
            counts1= getCount(s1);
            countTem=getCount(tem);
            confidence=countTem*1.0/counts1;

            if(confidence>=MIN_CONF)
            {
                System.out.print("关联规则："+ s1.toString()+"=>>"+s2.toString()+"   ");
                return confidence;
            }
            else {
                return 0;
            }
        }
        else {
            return 0;
        }
    }

    public static int getCount(List<String> in)//根据频繁项集得到其支持度计数
    {
        int rt=0;
        for(int i=0;i<map.size();i++)
        {
            Mymap tem=map.get(i);
            if(tem.isListEqual(in)) {
                rt = tem.getcount();
                return rt;
            }
        }
        return rt;

    }

    public static  List<String> gets2set(List<String> tem, List<String> s1)//计算tem减去s1后的集合即为s2
    {
        List<String> result=new ArrayList<>();

        for(int i=0;i<tem.size();i++)
        {
            String t=tem.get(i);
            if(!s1.contains(t)) {
                result.add(t);
            }
        }
        return  result;
    }


    public static List<List<String>> getSubSet(List<String> set){
        List<List<String>> result = new ArrayList<>();
        int length = set.size();
        /**
         * 2的n次方，若集合set为空，num为0；若集合set有4个元素，那么num为16.
         */
        int num = length==0 ? 0 : 1<<(length);

        //从0到2^n-1（[00...00]到[11...11]）
        for(int i = 1; i < num-1; i++){
            List<String> subSet = new ArrayList<>();
            int index = i;
            for(int j = 0; j < length; j++){
                if((index & 1) == 1){
                    subSet.add(set.get(j));
                }
                index >>= 1;
            }
            //把子集存储起来
            result.add(subSet);
        }
        return result;
    }
    public  static  boolean  AddToFrequenceItem(List<List<String>> fre)
    {

        for(int i=0;i<fre.size();i++)
        {
            Collections.sort(fre.get(i));
            frequentItemset.add(fre.get(i));
        }
        return true;
    }


    /**
     * 在每个频繁集的项后加频率count;
     * @param CandidateItemset
     */
    public static  void ShowData(List<List<String>> CandidateItemset)//显示出candidateitem中的所有的项集
    {
        for(int i=0;i<CandidateItemset.size();i++){
            List<String> list = new ArrayList<String>(CandidateItemset.get(i));
            for(int j=0;j<list.size();j++){
                System.out.print(list.get(j)+" ");
            }
            System.out.println(countFrequent1(CandidateItemset.get(i)));
        }
    }




    /**
     *********************** 有当前频繁项集自连接求下一次候选集 ********************************
     */
    private static List<List<String>> getNextCandidate(List<List<String>> FrequentItemset) {
        List<List<String>> nextCandidateItemset = new ArrayList<List<String>>();

        for (int i=0; i<FrequentItemset.size(); i++){
            HashSet<String> hsSet = new HashSet<String>();
            HashSet<String> hsSettemp = new HashSet<String>();
            for (int k=0; k< FrequentItemset.get(i).size(); k++) {
                hsSet.add(FrequentItemset.get(i).get(k));
            }
            //添加前长度
            int hsLength_before = hsSet.size();
            hsSettemp=(HashSet<String>) hsSet.clone();
            //频繁集第i行与第j行(j>i)连接   每次添加且添加一个元素组成    新的频繁项集的某一行，
            for(int h=i+1; h<FrequentItemset.size(); h++){
                //！！！做连接的hasSet保持不变
                hsSet=(HashSet<String>) hsSettemp.clone();
                for(int j=0; j< FrequentItemset.get(h).size();j++) {
                    hsSet.add(FrequentItemset.get(h).get(j));
                }
                int hsLength_after = hsSet.size();
                //如果不相等，表示添加了1个新的元素       同时判断其不是候选集中已经存在的一项
                if(hsLength_before+1 == hsLength_after && isnotHave(hsSet,nextCandidateItemset)){
                    Iterator<String> itr = hsSet.iterator();
                    List<String> tempList = new ArrayList<String>();
                    while(itr.hasNext()){
                        String Item = (String) itr.next();
                        tempList.add(Item);
                    }
                    nextCandidateItemset.add(tempList);
                }

            }

        }
        return nextCandidateItemset;
    }



    /**
     * 判断新添加元素形成的候选集是否在新的候选集中
     * listA.containsAll(listB);
     * 当项顺序不同时也判定为同一个元素；
     */
    private static boolean isnotHave(HashSet<String> hsSet, List<List<String>> nextCandidateItemset) {
        List<String>  tempList = new ArrayList<String>();
        Iterator<String> itr = hsSet.iterator();
        /**
         * 将hsset转换为List<String>
         */
        while(itr.hasNext()){
            String Item = (String) itr.next();
            tempList.add(Item);
        }
        for(int i=0; i<nextCandidateItemset.size();i++) {
            if (tempList.containsAll(nextCandidateItemset.get(i)) && nextCandidateItemset.get(i).containsAll(tempList)) {
                return false;
            }
        }
        return true;
    }


    /**
     * 由k项候选集剪枝得到k项频繁集
     */
    private static List<List<String>> getSupprotedItemset(List<List<String>> CandidateItemset) { //对所有的进行支持度计数
        // TODO Auto-generated method stub
        boolean end = true;
        List<List<String>> supportedItemset = new ArrayList<List<String>>();

        for (int i = 0; i < CandidateItemset.size(); i++){

            int count = countFrequent1(CandidateItemset.get(i));
            if (count >= MIN_SUP){
                supportedItemset.add(CandidateItemset.get(i));
                //存储当前频繁项集以及它的支持度计数
                map.add(new Mymap(CandidateItemset.get(i),count));
                end = false;
            }
        }
        //存在频繁项集则不会结束
        endTag = end;
        if(endTag==true) {
            System.out.println("*****************无满足支持度的" + times + "项集,结束连接");
        }
        return supportedItemset;
    }




    /**
     * 统计data2DList中出现list集合的个数
     */
    private static int countFrequent1(List<String> list) {//遍历所有数据集data2DList，对单个候选集进行支持度计数

        int count =0;
        //从data2DList的第一个开始遍历
        for(int i=0;i<data2DList.size();i++)
        {
            boolean flag=true;
            //如果data2DList中的第一个数据集包含list中的所有元素
            for (int j=0;j<list.size();j++)
            {
                String t=list.get(j);
                if(!data2DList.get(i).contains(t)) {
                    flag = false;
                    break;
                }
            }
            if(flag) {
                count++;
            }
        }
        //返回支持度计数
        return count;

    }


    /**
     * 获得一项候选集
     * @return
     */
    private static List<List<String>> findFirstCandidate() {
        // TODO Auto-generated method stub
        List<List<String>> tableList = new ArrayList<List<String>>();
        /**
         * 新建一个hash表，存放所有的不同的一维数据
         */
        HashSet<String> hs  = new HashSet<String>();
        /**
         * 遍历所有的数据集，找出所有的不同的数据存放到hs中
         */
        for (int i = 1; i<data2DList.size(); i++){
            for(int j=1;j<data2DList.get(i).size();j++){
                hs.add(data2DList.get(i).get(j));
            }
        }
        Iterator<String> itr = hs.iterator();
        while(itr.hasNext()){
            List<String>  tempList = new ArrayList<String>();
            String Item = (String) itr.next();
            /**
             * 将每一种数据存放到一个List<String>中
             */
            tempList.add(Item);
            /**
             * 所有的list<String>存放到一个大的list中
             */
            tableList.add(tempList);
        }
        return tableList;
    }
}
